/*
 * @lc app=leetcode.cn id=1670 lang=javascript
 *
 * [1670] 设计前中后队列
 */

// @lc code=start

var FrontMiddleBackQueue = function () {
  // 两个双端队列
  this.left = new Deque();
  this.right = new Deque();
};

/**
 * @param {number} val
 * @return {void}
 */
FrontMiddleBackQueue.prototype.balance = function () {
  if (this.left.size - this.right.size === 2) {
    this.right.insertFront(this.left.deleteLast());
  } else if (this.right.size > this.left.size) {
    this.left.insertLast(this.right.deleteFront());
  }
};
/**
 * @param {number} val
 * @return {void}
 */
FrontMiddleBackQueue.prototype.pushFront = function (val) {
  this.left.insertFront(val);
  this.balance();
};

/**
 * @param {number} val
 * @return {void}
 */
FrontMiddleBackQueue.prototype.pushMiddle = function (val) {
  if (this.left.size === this.right.size + 1) {
    this.right.insertFront(this.left.getRear());
    this.left.deleteLast();
  }
  this.left.insertLast(val);
  this.balance();
};

/**
 * @param {number} val
 * @return {void}
 */
FrontMiddleBackQueue.prototype.pushBack = function (val) {
  this.right.insertLast(val);
  this.balance();
};

/**
 * @return {number}
 */
FrontMiddleBackQueue.prototype.popFront = function () {
  if (this.left.size === 0) return -1;
  let val = this.left.getFront();
  this.left.deleteFront();
  this.balance();
  return val;
};

/**
 * @return {number}
 */
FrontMiddleBackQueue.prototype.popMiddle = function () {
  if (this.left.size === 0) return -1;
  let val = this.left.getRear();
  this.left.deleteLast();
  this.balance();
  return val;
};

/**
 * @return {number}
 */
FrontMiddleBackQueue.prototype.popBack = function () {
  if (this.left.size === 0 && this.right.size === 0) return -1;
  let val = this.right.size ? this.right.deleteLast() : this.left.deleteLast();
  this.balance();
  return val;
};

// 链表节点
class Node {
  constructor(val = null, next = null, prev = null) {
    this.val = val;
    this.next = next;
    this.prev = prev;
  }
}

// 双端队列
class Deque {
  constructor() {
    this.size = 0;
    this.head = new Node('head');
    this.tail = new Node('tail');
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  insertFront(value) {
    let node = new Node(value);
    let next = this.head.next;
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next = node;
    next.prev = node;
    this.size++;
  }
  insertLast(value) {
    let node = new Node(value);
    let prev = this.tail.prev;
    node.prev = prev;
    node.next = this.tail;
    this.tail.prev = node;
    prev.next = node;
    this.size++;
  }
  deleteFront() {
    if (this.isEmpty()) return false;
    let val = this.head.next.val;
    this.head.next = this.head.next.next;
    this.head.next.prev = this.head;
    this.size--;
    return val;
  }
  deleteLast() {
    if (this.isEmpty()) return false;
    let val = this.tail.prev.val;
    this.tail.prev = this.tail.prev.prev;
    this.tail.prev.next = this.tail;
    this.size--;
    return val;
  }
  getFront() {
    if (this.isEmpty()) return -1;
    return this.head.next.val;
  }
  getRear() {
    if (this.isEmpty()) return -1;
    return this.tail.prev.val;
  }
  isEmpty() {
    return this.size === 0;
  }
}

/**
 * Your FrontMiddleBackQueue object will be instantiated and called as such:
 * var obj = new FrontMiddleBackQueue()
 * obj.pushFront(val)
 * obj.pushMiddle(val)
 * obj.pushBack(val)
 * var param_4 = obj.popFront()
 * var param_5 = obj.popMiddle()
 * var param_6 = obj.popBack()
 */
// @lc code=end
